\documentclass[a4paper, 11pt]{article}
\usepackage[utf8]{inputenc} 
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{graphicx}
\usepackage[french]{babel}
\usepackage{fullpage}
\usepackage{pdfpages}
\usepackage{hyperref}

\graphicspath{{illustrations/}}

\begin{document}



\title{\includegraphics[width=7cm]{LogoIsticRvbFr}\\AS\\Classification des phonèmes à l'aide de différentes méthodes d'apprentissage supervisé}
\author{François Lehericey\\
   \texttt{francois.lehericey@insa-rennes.fr}\\
   Morgan Le Chénéchal\\
   \texttt{morgan.le-chenechal@insa-rennes.fr}}
\date{\today}
 
\maketitle

\thispagestyle{empty}

\newpage

\tableofcontents

\newpage

\section{Introduction}

Ce rapport a pour objectif de comparer différentes méthodes d'apprentissage supervisés.
Nous allons particulièrement nous intéresser aux résultats obtenus en fonction de différents 
paramètres choisis pour construire des arbres de décision, puis nous comparerons les résultats 
obtenus avec ceux atteint à l'aide d'un SVM, d'un réseau de neurones puis d'un apprentissage bayésien.
Pour ce faire, nous avons utilisé \texttt{weka}, ainsi qu'un logiciel développé à l'INSA l'an 
passé, \texttt{FAF} (Fast And Furious : Decision Tree Induction Bagging Begins - \texttt{FAFDTIBB}), 
qui offre la possiblité de gérer plusieurs Go de données en entrée d'un algorithme distribué 
de construction d'arbres de décision (cf. annexe \ref{annexe_faf}).

\section{Description des données}
Le jeu de données utilisé pour ces expériences est \texttt{phoneme}. Il pèse 4,5Go et est 
composé de 5,5 millions d'exemples avec 138 attributs numériques. L'ensemble de test est 
composé de 282 504 instances. Les exemples sont divisés en 4 classes qui représentes les 4 
grandes classes de phonèmes utilisées pour la reconnaissance vocale (fr, noSp, pl et vgn). 
Les attributs représentent des mesures effectuées sur la parole humaine. Le but de 
l'apprentissage sur cet ensemble est d'aider la reconnaissance vocale en étant capable pour 
un échantillon donné de prédire la classe du phonème.

Ce jeu de données est connu pour être difficile à classer et les meilleurs classifieurs ont 
du mal à descendre en dessous de 17\% d’erreur.

Cette difficulté provient en partie de la taille du corpus d'apprentissage car la plupart 
des logiciels d’apprentissage chargent en mémoire physique la totalité des données, ce qui n'est 
pas possible ici.
Pour pallier à ce problème avec \texttt{weka} nous avons utilisé des sous-ensembles issue de 
l'ensemble d'apprentissage, ainsi nous avons limité le corpus d'apprentissage à 5000 instances. 
L'ensemble de test ne sera pas restreint car l'évaluation de l'erreur ne demande pas de charger
le fichier de test en mémoire.
Concernant \texttt{FAF}, celui-ci étant conçu pour traiter de grand volumes de données il sera 
capable de traiter l'ensemble du corpus d'apprentissage et du jeu de test.

Une autre difficulté est la mauvaise distribution des classes, le tableau suivant montre la 
proportion de chaque classe dans le corpus d'apprentissage. On remarque que plus de la moitié 
des exemples sont étiquetés par la même classe. Cette mauvaise distribution à un impact direct 
sur les performances de classification, notamment pour les classes peu présentes.

\begin{center}
\begin{tabular}{c|c}
classe & pourcentage d'exemples\\
\hline 
fr & 14 \%\\
noSp & 12 \%\\
pl & 21 \%\\
vgn & 53 \%
\end{tabular}
\end{center}

Dans la suite, toute les erreurs sont des estimation de l'erreur réelle calculée à partir de 
l'ensemble de test complet.

\section{Arbre de décision}

\subsection{Validation de \texttt{FAF} en classification}

\subsubsection{Validation stricte}

Tout d'abord, nous avons validé l'algorithme de construction de \texttt{FAF} en comparant 
l'arbre calculé avec celui obtenu avec \texttt{weka}.
La construction a été réalisé sans élagage puisque \texttt{FAF} n'a pas implémenté cet 
algorithme : étant donné son contexte d'utilisation (gros volumes de données) \texttt{FAF} ne 
construit jamais l'arbre maximal, d'autres critères sont utilisés pour limiter la profondeur de 
construction (gain minimum, nombre minimum d'exemples et hauteur maximale).

Paramètres de construction :
\begin{itemize}
 \item Taille de l'ensemble d'apprentissage : 1000
 \item Nombre d'exemples minimum par feuille : 50
\end{itemize}

\begin{figure}
\begin{center}
 \includegraphics[width=\textwidth]{../DT1000_50exbyleaf/weka_nopruning.png}
 \caption{\texttt{weka}}
 \label{arbreW}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
 \includegraphics[width=\textwidth]{../DT1000_50exByLeaf_FAF/all1000.png}
 \caption{\texttt{FAF}}
 \label{arbreF}
\end{center}
\end{figure}

En comparant en détail les 2 arbres obtenus (figures \ref{arbreW} et \ref{arbreF}), à partir de 
ce petit exemple de construction d'arbre de décision, on peut conclure que \texttt{FAF} et 
\texttt{weka} implémente un algorithme de construction comparable. En effet, de nombreuses 
questions sont identiques d'un arbre à l'autre, par exemple les racines sont les mêmes. \\
Pour être certain de pouvoir comparer les capacités de classification des 2 algorithmes, il
convient de comparer des métriques de performances sur cet exemple. \\

\begin{center}
\begin{tabular}{c|ccc}
Logiciel & Précision & Rappel & Erreur réelle\\
\hline 
\texttt{weka} & 69 \% & 67 \% & 34 \%\\
\texttt{FAF} & 69 \% & 53 \% & 36 \%
\end{tabular}
\end{center}

Ainsi on peut facilement se persuader que \texttt{weka} et \texttt{FAF} construisent des 
classifieurs comparables.

\subsubsection{Limitations}

Nous avons démontré dans la partie précédente que \texttt{FAF} et \texttt{weka} implémentent 
des algorithmes de construction d'arbre comparable.\\
Cependant, nous pouvons constater des différences entre les 2 logiciels.\\ \\
Premièrement on constate que des questions sont présentes dans les 2 arbres mais ne sont pas 
au même niveau dans l'arbre ; par exemple la question sur l'attribut \texttt{yafee.obsi\_4\_m2\_1} 
avec un seuil égal à 0.01. Ceci s'explique car l'algorithme de construction diffère légèrement 
dans certains calculs.\\

Deuxièmement, \texttt{weka} implémente un algorithme d'élagage, ce que ne fait pas \texttt{FAF}.
On va donc comparer les performances de classification entre le même arbre construit par \texttt{weka},
avec ou sans élagage.\\ \\

Paramètres de construction :
\begin{itemize}
 \item Taille de l'ensemble d'apprentissage : 5000
 \item Nombre d'exemples minimum par feuille : 2
\end{itemize}

\begin{center}
\begin{tabular}{c|c}
 & Erreur réelle\\
 \hline 
Sans élagage & 35 \%\\
Avec élagage & 31 \%\\
\end{tabular}
\end{center}

L'élagage permet donc de gagner 4 \% sur l'erreur réelle du classifieur ce qui n'est pas étonnant
puisque l'on distingue clairement un sur-apprentissage sur l'arbre non-élagué, puisque son erreur
réelle a augmenté de 1 \% par rapport au même arbre construit avec 1000 exemples dans la partie précédente.
En effet, ici on limite le nombre d'instances dans les feuilles à 2, ce qui implique une spécialisation
du classifieur sur les données d'apprentissage.\\
L'élagage permet donc de supprimer cette spécialisation, donc de gagner en généralisation
et de diminuer l'erreur réelle.\\


\subsection{Améliorations des performances}

\subsubsection{Passage à l'échelle}
On a constaté dans la partie précédente que l'élagage couplé à l'augmentation de la taille de l'ensemble
d'apprentissage permettait de gagner en terme de performances de classification.
Cependant nous ne sommes arrivé qu'à une erreur réelle de 31 \% au mieux, ce qui est plutôt
médiocre, mais normal étant donné la difficulté à classifier la base de données \texttt{phoneme}. \\
Cette base contient initialement 5,5 millions d'exemples ; cependant \texttt{weka} ne peut pas gérer
un si volumineux ensemble d'apprentissage. Pourtant, le seul moyen de diminuer l'erreur réelle
de classification est clairement de prendre en compte toute la base pour construire l'arbre de
décision. \\
Pour preuve, voici les résultats obtenus avec \texttt{FAF} à partie de la base complète : \\

Paramètres de construction :
\begin{itemize}
 \item Taille de l'ensemble d'apprentissage : 5.500.000
 \item Nombre d'exemples minimum par feuille : 100
\end{itemize}

\begin{center}
\begin{tabular}{ccccc}
Temps de calcul & Nombre de coeurs & Précision & Rappel & Erreur réelle\\
\hline
42 minutes & 50 & 77.1 \% & 72.7 \% & 20.3 \%\\
\end{tabular}
\end{center}

Le passage à l'échelle permet donc bien de diminuer drastiquement les erreurs de classification
de l'arbre de décision produit.

\subsubsection{Bagging}

Le meta-algorithme d'apprentissage de bagging, couplé au fait d'avoir la capacité de traiter l'ensemble 
de la base de données d'apprentissage, permet encore de diminuer l'erreur réelle du classifieur produit.\\
La figure \ref{bagging} montre les résultats obtenus dans ce contexte avec \texttt{FAF}. On arrive alors à 
baisser l'erreur réelle jusqu'à 17.6 \% avec 200 arbres construits dans le bagging.\\
On peut donc bien augmenter les performances de classification grâce au système de vote introduit
par le bagging.\\ \\

\begin{figure}[h]
\begin{center}
 \includegraphics[width=10cm]{./illustrations/bagging2.jpg}
 \caption{Bagging}
 \label{bagging}
\end{center}
\end{figure}

Remarque : les arbres composant ce dernier classifieur ont été construit chacun avec un sous-ensemble
aléatoire fesant 5 \% de la base initiale (environ 225.000 exemples). Le classifieur complet a été
construit en 185 minutes sur 240 coeurs.



\section{SVM}

Paramètres globaux de construction :
\begin{itemize}
\item Taille de l'ensemble d'apprentissage : 5000
\item Les attributs sont normalisés.
\item Stratégie multi-classes: one-versus-one
\end{itemize}

Nous avons testé des SVM pour classifier les données. Nous avons utilisé des noyaux 
polynomiaux $K(x,y) = <x,y>^{n}$ avec différentes valeurs de n. Les résultats sont présentés dans la 
table suivante:

\begin{center}
\begin{tabular}{c|cc}
n & Temps de calcul & Taux d'erreur réelle\\
\hline
1 & 2,6 s & 26 \%\\
2 & 143 s & 26.5 \%\\
3 & 519 s & 32 \%\\
4 & 340 s & 31.6 \%
\end{tabular}
\end{center}

Les meilleurs résultats sont obtenus avec n = 1, ce qui signifie que la projection associée contient 
les combinaisons les plus significatives. En passant à des valeurs de n supérieurs, le taux d'erreur 
augmente, ce qui signifie que les projections ne contiennent pas les bonnes combinaisons d'attributs.

\section{Réseaux de neurones}

Paramètres globaux de construction :
\begin{itemize}
 \item Fonction de transfert : sigmoid
 \item Nombre de neurones par couches cachées : $\frac{nombre d'attributs + nombres de classes}{2} = 71$
\end{itemize}

\begin{center}
\begin{tabular}{p{3cm}p{3cm}p{3cm}p{3cm}p{2cm}}
Taille de l'ensemble d'apprentissage & Nombre de niveau caché & Nombre d'époques (N) & Temps de calcul & Taux d'erreur réelle\\
\hline
500 & 1 & 5 & 5.7 s & 32.5 \%\\
500 & 1 & 50 & 55 s & 39.7 \%\\
500 & 1 & 500 & 604 s & 43 \%\\
5000 & 1 & 50 & 677 s & 25.3 \%\\
\hline
500 & 2 & 5 & 10.3 s & 38.5 \%\\
5000 & 2 & 5 & 106 s & 29.5 \%\\
5000 & 2 & 50 & 1254 s & 23.9 \%
\end{tabular}
\end{center}

Ces résultats démontrent clairement que pour un nombre d'instances d'apprentissage trop faible, 
plus l'algorithme boucle, plus il se spécialise sur les données et perd donc de son pouvoir de 
généralisation. La seule manière de diminuer l'erreur réelle est d'augmenter le taille de l'ensemble 
d'apprentissage. Ici, on remarque que la gain est assez important puisqu'on arrive alors à 25.3 \%
d'erreur, ce qui est plutôt bon pour ce jeu de données en considérant que l'on utilise que
5000 exemples pour l'apprentissage.\\

L'ajout d'une couche cachée avec 500 exemples provoque une diminution des performances, 
cet effet est probablement dû à l'augmentation de l’expressivité du réseau qui permet un sur-apprentissage. 
En revanche, avec 5000 exemples les performances sont améliorées. Cet effet peut s'expliquer par le 
rapport \texttt{nombre d'instances d'apprentissage/nombre total de neurones du réseau}. Si ce rapport est 
trop faible (ce qui est le cas avec 500 exemples), le réseau se spécialise trop fortement au fur et à 
mesure des itérations. Au contraire, avec 5000 exemples, l'augmentation du nombre d'itération améliore 
les performances.

\section{Apprentissage bayésien}

Paramètres globaux de construction :
\begin{itemize}
\item Taille de l'ensemble d'apprentissage : 5000
\end{itemize}

L'apprentissage bayésien permet d'atteindre un taux d'erreur de 24.5\%. En revanche le rappel est très 
faible pour la classe noSp, car cette classe est très peut présente.
\section{Conclusion}

On ne pourra malheureusement pas comparer les temps de calculs des différentes méthodes entre elles, 
car les expériences ont été réalisées sur différentes machines.\\

Le tableau suivant résume les meilleurs performances que nous avons obtenus avec \texttt{weka}.

\begin{center}
\begin{tabular}{c|cc}
Méthode & Taux d'erreur réelle\\
\hline
Arbre de décision & 31\%\\
SVM & 26\%\\
Réseaux de neurones & 23.9\%\\
Apprentissage bayésien & 24.5\%\\
\end{tabular}
\end{center}

Ces résultats ont été obtenus en utilisant un ensemble qui ne contient que 5000 instances. À l'aide 
de \texttt{FAF} nous avons été capable de traiter entièrement le corpus composé de 5.5 millions 
d'instances et de construire un arbre dont l'erreur réelle est de 20.3\%. Ce résultat est meilleur que 
tout ceux atteint avec \texttt{weka}, alors que les arbres de décision ont les moins bonnes performances 
avec \texttt{weka}. Il aurait été intéressant de pouvoir tester les autres méthodes d'apprentissage 
avec le corpus complet, malheureusement \texttt{weka} ne le permet pas à cause de limitations mémoire.\\

Nous n'avons pas testé avec \texttt{weka} des méthodes de méta-apprentissage. En revanche avec \texttt{FAF} 
nous avons réussi à atteindre 17.6\% d'erreur en utilisant le bagging, ce qui est un score se rapprochant 
des meilleurs performances actuelles sur ce jeu de données.

\appendix

\section{Annexes}

\subsection{Fast And Furious : Decision Tree Induction Bagging Begins}
\label{annexe_faf}

Ce logiciel implémente un algorithme distribué de construction d'arbres de décision.
Il utilise le paradigme Map/Reduce implémenté par le framework Hadoop Java.
De plus, un algorithme de meta-apprentissage, le bagging, a aussi été implémenté en distribué.
Enfin, on peut ajouter que \texttt{FAF} gère également l'interrogation à partir de jeu de test afin d'obtenir des résultats de performances en classification des arbres calculés.
\texttt{FAF} a été conçu pour s'exécuter sur une grille de calcul, et a été testé sur le Grid'5000.
Il a été développé dans le cadre d'un projet courant sur toute la 4ème année au département informatique de l'INSA de Rennes par Fabien Andre, Manon Barthelemy, Nadia Boumadhi, François Lehericey, Morgan Le Chénéchal et Pierre Wilke.
Une particularité de \texttt{FAF} est de gérer à la fois des très gros volumes de données (plusieurs Go) à l'aide de Map/Reduce, mais également des volumes de données plus raisonables (ceux en entrée de noeuds profonds dans l'arbre) grâce au même algorithme implémenté directement en mémoire et lancé sur différentes machines de la grille.
L'algortihme global détecte automatiquement le seuil et "switch" de mode afin de tirer les meilleurs performances en terme de temps de calcul.

Ainsi, \texttt{FAF} a été testé et a montré qu'il pouvait construire 200 arbres à partir de 4,5Go de données (tous paramètres bien choisis) en 3h, ce qui paraît tout à fait acceptable.
Celà est une innovation dans le sens où des logiciels comme \texttt{weka} ne peuvent pas gérer autant de volume de données (puisque tout est fait en mémoire local) ou comme BonzaiBoost qui peuvent gérer des gros volumes d'entrée sur une très grosse machine multi-coeurs, mais les temps de calcul sont bien supérieur à ceux obtenus par \texttt{FAF} sur une grille de calcul.

Cependant, les performances en terme de classification n'ont pas été assez comparé à des résultats obtenus avec d'autres logiciels.
En effet, le fait de pouvoir gérer autant de volumes et de pouvoir utiliser le bagging permet d'obtenir des résultats très intéressants, et c'est ce que nous montrons dans ce rapport.

\end{document}

